\documentclass[11pt,a4paper]{article}

\usepackage{tabularx}
\usepackage[utf8x]{inputenc}
\usepackage[french]{babel}
\usepackage{geometry}
\usepackage[table]{xcolor}
\usepackage{graphicx}
\usepackage{fancyhdr}

% yen a des conneries, mais il manque le plus important.
\usepackage{amsmath}

\geometry{a4paper}

\makeatletter

\definecolor{borderBlue}{RGB}{84,141,212}
\definecolor{textBlue}{RGB}{54,95,145}
\definecolor{blue}{RGB}{198, 217, 241}

\def\thickhrulefill{\leavevmode \leaders \hrule height 1pt\hfill \kern \z@}

% la commande \newtitlingelement permet de créer des commandes du type \title, \author ou \date
\newcommand{\newtitlingelement}[1]{%
  \expandafter\newcommand\csname the#1\endcsname{}%
  \expandafter\newcommand\csname #1\endcsname[1]{\expandafter\renewcommand\csname the#1\endcsname{##1}}%
}

\newtitlingelement{version}
\newtitlingelement{desc}

\def\subsection{\@ifstar\unnumberedsubsection\numberedsubsection}
\def\numberedsubsection{\@ifnextchar[%]
  \numberedsubsectionwithtwoarguments\numberedsubsectionwithoneargument}
\def\unnumberedsubsection{\@ifnextchar[%]
  \unnumberedsubsectionwithtwoarguments\unnumberedsubsectionwithoneargument}
\def\numberedsubsectionwithoneargument#1{\numberedsubsectionwithtwoarguments[#1]{#1}}
\def\unnumberedsubsectionwithoneargument#1{\unnumberedsubsectionwithtwoarguments[#1]{#1}}
  
  
\def\numberedsubsectionwithtwoarguments[#1]#2{%
  \ifhmode\par\fi
  \removelastskip
  \vskip 3ex\goodbreak
  \refstepcounter{subsection}%
  \hbox to \textwidth{%
      \hss\vbox{\advance\textwidth by 1cm
      \noindent
      \leavevmode\Large\bfseries\raggedright
      \textcolor{textBlue}{\thesubsection\ }
      \textcolor{textBlue}{#2}\par
      \vskip -2ex
      \noindent\textcolor{blue}{\dotfill}
      }}\nobreak
  \vskip 2mm\nobreak
  \addcontentsline{toc}{subsection}{%
    \protect\numberline{\textcolor{textBlue}{\thesubsection}}%
    \textcolor{textBlue}{#1}}%
  \ignorespaces
}  

\def\unnumberedsubsectionwithtwoarguments[#1]#2{%
  \ifhmode\par\fi
  \removelastskip
  \vskip 3ex\goodbreak
  \refstepcounter{subsection}%
  \hbox to \textwidth{%
      \hss\vbox{\advance\textwidth by 1cm
      \noindent
      \leavevmode\Large\bfseries\raggedright
      %\textcolor{textBlue}{\thesubsection\ }
      \textcolor{textBlue}{#2}\par
      \vskip -2ex
      \noindent\textcolor{blue}{\dotfill}
      }}\nobreak
  \vskip 2mm\nobreak
  \addcontentsline{toc}{subsection}{%
   % \protect\numberline{\textcolor{textBlue}{\thesubsection}}%
    \textcolor{textBlue}{#1}}%
  \ignorespaces
}  
  


\def\section{\@ifstar\unnumberedsection\numberedsection}
\def\numberedsection{\@ifnextchar[%]
  \numberedsectionwithtwoarguments\numberedsectionwithoneargument}
\def\unnumberedsection{\@ifnextchar[%]
  \unnumberedsectionwithtwoarguments\unnumberedsectionwithoneargument}
\def\numberedsectionwithoneargument#1{\numberedsectionwithtwoarguments[#1]{#1}}
\def\unnumberedsectionwithoneargument#1{\unnumberedsectionwithtwoarguments[#1]{#1}}



\def\numberedsectionwithtwoarguments[#1]#2{%
  \ifhmode\par\fi
  \removelastskip
  \vskip 5ex\goodbreak
  \refstepcounter{section}%
  \hbox to \hsize{\hss\vbox{\advance\hsize by 1cm
      \noindent
      \leavevmode\Large\bfseries\raggedright
      \fcolorbox{borderBlue}{blue}{\makebox[\hsize][l]{\textcolor{textBlue}{\thesection.\ #2}}}\par
      \vskip -2ex
      }}\nobreak
  \vskip 2ex\nobreak
  \addcontentsline{toc}{section}{%
    \protect\numberline{\textcolor{textBlue}{\thesection}}%
    \textcolor{textBlue}{#1}}%
 }
 
\def\unnumberedsectionwithtwoarguments[#1]#2{%
  \ifhmode\par\fi
  \removelastskip
  \vskip 5ex\goodbreak
  \refstepcounter{section}%
  \hbox to \hsize{\hss\vbox{\advance\hsize by 1cm
      \noindent
      \leavevmode\Large\bfseries\raggedright
      \fcolorbox{borderBlue}{blue}{\makebox[\hsize][l]{\textcolor{textBlue}{ #2}}}\par
      \vskip -2ex
      }}\nobreak
  \vskip 2ex\nobreak
  \addcontentsline{toc}{section}{%
    %\protect\numberline{\textcolor{textBlue}{\thesection}}%
    \textcolor{textBlue}{#1}}%
 }


\makeatother

\author{FIXME j'aime pas mettre mon nom dans le nuage}
\title{Document introductif : projet EIT moteur de recherche}
\date{\today}

\begin{document}
\maketitle
\tableofcontents
% newpage c'est MAL. Ça veut dire que l'on sais pas mettre en page.
\newpage
\section{Prérequis}
	\subsubsection*{Langage}
		On choisie de développer le programme en C++.
		
	\subsubsection*{Système d'exploitation}
		Le projet doit marcher avec un système linux.
		
	\subsubsection*{Modèle}
		Le projet doit implémenter le modèle booléen étendu, il devra supporter le "et" et le "ou".
		Il faut un modèle capable de chercher vite, l'indexation peut \^etre plus lente.
		Il faut pouvoir stocker l'index pour ne pas avoir à le recalculer à chaque utilisation.
		
\section{Index}
\subsection{Fonctionnalités}
Selon les fonctionnalités requises par le moteur de recherche, plusieurs fonctionnalités de l'index peuvent être nécessaire.

\subsubsection{Chargement rapide}
Il faut que l'index puisse être chargé rapidement, et ne prenne pas beaucoup de place en mémoire une fois chargé.

\subsubsection{Recherche inverse}
Le but d'un moteur de recherche est de pouvoir retrouver les documents contenant un certain mot ou lemme. Il faut
donc pouvoir retrouver une liste de documents à partir d'un lemme de manière efficace.

Puisqu'on utilise le modèle booléen étendu, il est également nécessaire de stocker le TF-IDF du terme.
\subsubsection{Surlignage des résultats}
Pour pouvoir identifier rapidement si un résultat est pertinent, il est souvent utile de mettre un extrait du texte autour des mots de la requête. Pour cela il faut stocker la position du mot dans le texte ou dans le fichier source, et il faut être capable de reconstituer le texte original.

\subsubsection{Recherche littérale}
Pour pouvoir effectuer des recherches littérales, il faut pouvoir stocker la position des occurrences des mots dans
les textes cherchés.

\newcommand{\treetagger}{\texttt{treetagger}}
\newcommand{\utf}{\texttt{UTF-8}}
\subsubsection{Encodage de caractère}
L'idéal serait de pouvoir supporter tout les types de caractères.
Or, le \treetagger{} ne supporte pas l'Unicode, donc il est inutile de supporter l'Unicode ou l'\utf{} dans notre programme;
On sera incapable d'effectuer une 
recherche sur des documents en \utf, étant donné que la première étape de la recherche est de lématiser l'entrée avec le \treetagger.

\subsection{Implémentation}
L'index prendra la forme d'un fichier qui sera ouvert grâce à ''\texttt{mmap()}'', une fonction POSIX permettant d'accéder à un fichier de la même manière que l'on accède à de la mémoire.
Cette fonction étant rapide mais ne mettant pas en mémoire le fichier tout entier, on pourra procéder à une lecture séquentielle pour être sur que les données sont chargées en mémoire.

On choisira de stocker les positions des objets de l'index (ci-après appelé "pointeurs) sur un entier de 32 bit.
La position des objets pourra être obtenue en multipliant la position par un facteur qui sera spécifié dans l'entête.
Cela fait qu'il est possible de construire des index de $2^{32}f$ octets, ou $f$ est le facteur considéré, qu'on limitera à une valeur de 16.

L'index contiendra un entête indiquant le facteur de position, et la position des éléments principaux.

On essayera de privilégier la localité des données pour augmenter les performances de lectures et de traitement.

\subsubsection{Table de documents}
Afin de pouvoir coder à quel document contient tel mot, il est utile de pouvoir stocker avec un seul nombre le numéro du document.
Pour cela, il faut pouvoir relier le numéro du document à son nom.
Pour cela on peut stocker un pointeur vers une entrée de document.
Une entrée de document est constituée de deux pointeurs pointant sur des morceau de chemin de fichiers, qui sont des chaines terminées par un \verb|\0|, et qui peuvent être partagés par plusieurs entrées de documents.

\subsubsection{Recherche inverse avec un arbre N-aire}
\newcommand{\noeud}{{n\oe ud}}
La recherche inverse à partir des lemmes se fera avec un arbre N-aire permettant un meilleur tri et facile à sérialiser.

Pour pouvoir accéder rapidement à un fils à partir d'un \noeud, il faudra implémenter une table de hachage pour ne pas avoir à parcourir tout les fils du \noeud.

\subsubsection{Table de hachage}
La table de hachage devra permettre de récupérer une entrée à partir d'un caractère en temps constant.

Une table de hachage est constituée d'un entête et d'une liste d'entrée.
%
L'entête contiendra les information suivantes :
\begin{itemize}
\item La taille $T$ de la table de hachage stocké sur un octet.
C'est le seul champ présent si la table est vide (taille = 0).
\item La borne inférieure $m$ des caractères présents dans la table, sur un octet.
\item Le facteur $f$ à appliquer dans la fonction de hachage, sur un octet elle aussi.
\end{itemize}
Les collisions ne seront pas gérées.
L'indéxateur sera responsable d'assurer l'absence de collisions.
Pour cela il peut augmenter la taille de la table de hachage, changer le facteur ou diminuer la borne minimale.

La fonction de hachage sera la suivante :
$f(c) = (c-m)f \bmod T$

Les entrées seront des simples pointeurs vers des \noeud s.
Comme les \noeud s contiennent leur caractère, on pourra contrôler l'existence d'un caractère en lisant le \noeud{} associé.
\subsubsection{Structure d'un \noeud}
Un \noeud{} est composé :
\begin{itemize}
\item D'un caractère.
%\item De trois octets qui servent à rien. (pour l'instant)
\item De la table de hachage vers les fils.
\item D'un pointeur vers des données détaillées.
\end{itemize}


Les données détailles contiennent :
\begin{itemize}
\item Du nombre de documents dans lequel le lemme apparait.
\item D'une liste de pointeurs vers des documents, les documents étant triés par \texttt{TF-IDF} décroissants.
\item D'une liste de \texttt{TF-IDF} du mot dans les documents. On choisi de stocker les \texttt{TF-IDF} des documents et non les idf, puisque dans les deux cas, on doit stocker la même quantité d'information.
\item D'une liste de pointeurs vers des postings (pour la recherche littérale).
\end{itemize}

Les postings (indice des mots dans le documents) sont composés de :
\begin{itemize}
\item Le nombre de fois ou le lemme apparait
\item D'une liste de postings
\item D'une liste d'offset dans le fichier considéré (pour le surlignage).
\end{itemize}

\end{document}
